#第18题. 四数之和
from typing import List
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #[-4,-1,0,0]   target=-5
        nums=sorted(nums)
        ans=[]

        for i in range(len(nums)):
            if nums[i]>target and target>0 and nums[i]>0:
                break

            if i>0 and nums[i-1]==nums[i]:
                continue

            for j in range(i+1,len(nums)):
                if nums[j]>target and target>0 and nums[j]>0:
                    break

                if j>i+1 and nums[j-1]==nums[j]:
                    continue

                left=j+1
                right=len(nums)-1
                while left<right:
                    sums=nums[i]+nums[j]+nums[left]+nums[right]
                    if sums>target:
                        right-=1
                    elif sums<target:
                        left+=1
                    else:
                        ans.append([nums[i],nums[j],nums[left],nums[right]])
                        while left<right and nums[left+1]==nums[left]:
                            left+=1
                        while left<right and nums[right-1]==nums[right]:
                            right-=1 
                        left+=1
                        right-=1

        return ans